Maximal rectangle [Mono Stack, DP]

Time: O(MxN); Space: O(N); hard

Given a 2D binary matrix filled with 0’s and 1’s,

find the largest rectangle containing all ones and return its area.

Example 1:

Input: matrix =

[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]

Output: 6

1. Ascending stack solution

[8]:

class Solution1(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        Ascending stack solution
        """
        def largestRectangleArea(heights):
            increasing, area, i = [], 0, 0
            while i <= len(heights):
                if not increasing or (i < len(heights) and heights[i] > heights[increasing[-1]]):
                    increasing.append(i)
                    i += 1
                else:
                    last = increasing.pop()
                    if not increasing:
                        area = max(area, heights[last] * i)
                    else:
                        area = max(area, heights[last] * (i - increasing[-1] - 1 ))
            return area

        if not matrix:
            return 0

        result = 0
        heights = [0] * len(matrix[0])
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                heights[j] = heights[j] + 1 if matrix[i][j] == '1' else 0
            result = max(result, largestRectangleArea(heights))

        return result

[14]:

s = Solution1()
matrix = [
    ["1","0","1","0","0"],
    ["1","0","1","1","1"],
    ["1","1","1","1","1"],
    ["1","0","0","1","0"]
]
assert s.maximalRectangle(matrix) == 6
matrix = ["01101",
          "11010",
          "01110",
          "11110",
          "11111",
          "00000"]
assert s.maximalRectangle(matrix) == 9

2. DP solution

[15]:

class Solution2(object):
    """
    DP solution:
    dp[i][j] = max length of all 1 sequence ends with col j, at the i-th row
    transition:
       dp[i][j] = 0 if matrix[i][j] == '0'
                = dp[i][j-1] + 1 if matrix[i][j] == '1'
    """
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0

        result = 0
        m = len(matrix)
        n = len(matrix[0])
        L = [0 for _ in range(n)]
        H = [0 for _ in range(n)]
        R = [n for _ in range(n)]

        for i in range(m):
            left = 0
            for j in range(n):
                if matrix[i][j] == '1':
                    L[j] = max(L[j], left)
                    H[j] += 1
                else:
                    L[j] = 0
                    H[j] = 0
                    R[j] = n
                    left = j + 1

            right = n
            for j in reversed(range(n)):
                if matrix[i][j] == '1':
                    R[j] = min(R[j], right)
                    result = max(result, H[j] * (R[j] - L[j]))
                else:
                    right = j

        return result

[16]:

s = Solution2()
matrix = [
    ["1","0","1","0","0"],
    ["1","0","1","1","1"],
    ["1","1","1","1","1"],
    ["1","0","0","1","0"]
]
assert s.maximalRectangle(matrix) == 6
matrix = ["01101",
          "11010",
          "01110",
          "11110",
          "11111",
          "00000"]
assert s.maximalRectangle(matrix) == 9